//============================================================================
// Name        : Sort.cpp
// Author      : Anton Kuchin
// Version     :
// Copyright   : Your copyright notice
// Description : Sorting uints from input file, writing output to output file, using mmap
//============================================================================

//TODO: clean unused includes
//FIXME: free all resources if any of operations fail
//TODO: implement sorting algorithms and strategy

#include <iostream>
#include <stdio.h>
#include <fstream>
#include <sys/mman.h>
#include <errno.h>

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <unistd.h>
#include <sys/mman.h>
#include <sys/ioctl.h>

#include <sys/stat.h>
#include <sys/sysmacros.h>

#include <fcntl.h>
#include <linux/fb.h>
#include <linux/input.h>

#include <assert.h>
#include <errno.h>
#include <limits.h>
#include <signal.h>

#include <string.h>

#include <unistd.h>
#include <sys/mman.h>
#include <sys/ioctl.h>

#include <sys/stat.h>

#include <fcntl.h>
#include <linux/fb.h>
#include <linux/input.h>

#include <assert.h>
#include <errno.h>
#include <limits.h>
#include <signal.h>

using namespace std;

#include "SortingAlgorythms.h"


//#define cout cout<<__FILE__<<" "<<__LINE__<<" "
#define BLOCKS_IN_CHUNK 30520
//#define BLOCKS_IN_CHUNK 16384
//#define BLOCKS_IN_CHUNK 2

//Global variables
char separator = ' ';
char defaultOutputFileName[] = "output/sort_out.txt";

//Helper functions
char* intToChar(int src, char* dst) {
	sprintf(dst, "%d%c", src, separator);
	return (dst);
}

//Stupid inconvinient functon, but it makes main() more compact
int convertArrOfCharsToInts(char* pMappedFile, long long numberOfChars, int* array, int& tail, char &separator, bool & first, bool last) {
	long count = 0;
	unsigned long temp = tail;
	int numberOfInts = 0;

	while (count < numberOfChars) {
		char currentChar = pMappedFile[count];
		if (currentChar != separator) {
			first = false;
			if (currentChar >= '0' && currentChar <= '9') {
				temp = temp * 10 + (currentChar - '0');
			} else {
				cout << "Something is wrong in your file. Unexpected character " << currentChar << " on position " << count << endl;
				exit(EXIT_FAILURE);
			}
			count++;
		} else {
			if (first) {
				count++;
			} else {
				if (temp <= UINT_MAX) {
					array[numberOfInts] = temp;
					numberOfInts++;
					temp = 0;
					count++;
					first = true;
				} else {
					cout << "Something is wrong in your file. Number " << temp << " on position " << count << " is larger than UINT_MAX and can't be processed\n" << endl;
					exit(EXIT_FAILURE);
				}
			}
		}
	}

	if (!last) {
		tail = temp;
		cout << "tail is " << tail << endl;
	} else {
		cout << "this is last so tail is correct" << endl;
		if (!first) {
			array[numberOfInts] = temp;
			numberOfInts++;
		}
	}

	return (numberOfInts);

}

//Class that encapsulates logic for working with memory mapped file
template<typename T>
class MappedFile {
public:
	int fileDescriptor;
	T* pMappedFile;
	char* fileName;
	struct stat fileStat;
	long long chunkSize;
	int numberOfChunks;
	int chunkIndex;

public:
	MappedFile(char* name, long long blocksInChunk, int permissions = O_RDWR, int size = 0, int mapProtection = PROT_READ) {
		pMappedFile = (T*) MAP_FAILED;
		fileName = new char[strlen(name)];
		strcpy(fileName, name);
		chunkSize = size;
		numberOfChunks = 0;
		chunkIndex = 0;

		fileDescriptor = open(fileName, permissions, (mode_t) 0644); //O_RDWR | O_CREAT | O_TRUNC

		if (fileDescriptor < 0) {
			cout << "Error opening file " << fileName << ": " << strerror(errno) << endl;
			exit(EXIT_FAILURE);
		}

		if (size != 0) {
			int result = lseek(fileDescriptor, size - 1, SEEK_SET);
			if (result == -1) {
				close(fileDescriptor);
				perror("Error calling lseek() to 'stretch' the file");
				exit(EXIT_FAILURE);
			}

			result = write(fileDescriptor, "", 1);
			if (result != 1) {
				close(fileDescriptor);
				perror("Error writing last byte of the file");
				exit(EXIT_FAILURE);
			}
		}
		stat(fileName, &fileStat);

		if (fileStat.st_size > fileStat.st_blksize * blocksInChunk) {
			cout << "File "<< fileName <<" is too big, so I need to slice it into smaller parts" << endl;
			chunkSize = fileStat.st_blksize * blocksInChunk;
			numberOfChunks = fileStat.st_size / fileStat.st_blksize / blocksInChunk;
			cout << fileName << ": number of chunks is " << numberOfChunks << endl;
		} else {
			chunkSize = fileStat.st_size - 1;
		}

		map(mapProtection);

	}

	~MappedFile() {
		if (pMappedFile != NULL) {
			unmap();
		}

		close(fileDescriptor);
		delete[](fileName);
	}
private:

	void map(int prot = PROT_READ) {
		cout <<fileName << ": started processing chunk #" << chunkIndex << endl;

		int currentChunkSize = min(chunkSize, fileStat.st_size - (chunkSize * chunkIndex) - 1);
		pMappedFile = (T*) mmap(NULL, currentChunkSize, prot, MAP_SHARED, fileDescriptor, chunkSize * chunkIndex);

		if (pMappedFile == MAP_FAILED) {
			cout << fileName << " Mapping failed: " << strerror(errno) << " " << errno << endl;
			exit(EXIT_FAILURE);
		}
		chunkSize = currentChunkSize;
		cout << "chunk mapped, size is " << chunkSize << endl;

	}

	void unmap() {
		munmap(pMappedFile, chunkSize);
		cout <<fileName << ": chunk #" << chunkIndex << " unmapped" << endl << endl;
	}

	void next() {
		if (chunkIndex < numberOfChunks) {
			unmap();
			chunkIndex++;
			map();
		} else {
			unmap();
			chunkIndex++;
			pMappedFile = NULL;
		}
	}

public:
	class Iterator {
	public:
		friend class MappedFile;
		Iterator() {

		}
		~Iterator() {

		}

	private:
		Iterator(int chunkNumber, MappedFile* mapping) {
			this->mapping = mapping;
			this->chunkNum = chunkNumber;
		}
		;
	public:

		Iterator& operator=(const Iterator& other) {
			mapping = other.mapping;
			chunkNum = other.chunkNum;
			return (*this);
		}

		bool operator==(const Iterator& other) {
			return ((chunkNum == other.chunkNum) && (mapping == other.mapping));
		}

		bool operator!=(const Iterator& other) {
			return ((chunkNum != other.chunkNum) || (mapping != other.mapping));
		}

		Iterator& operator++(int) {
			if (*this != mapping->end()) {
				mapping->next();
				chunkNum++;
			}
			return (*this);
		}

		Iterator& operator++() {
			return ((*this)++);
		}

		T*& operator*() { //TODO: check
			return (mapping->pMappedFile);
		}

		T** operator->() {
			return (&*(MappedFile::Iterator) *this);
		}

	private:
		int chunkNum;
		MappedFile<T> * mapping;
	};

	Iterator begin() {
		return (Iterator(0, this));
	}

	Iterator end() { //TODO: check
		return (Iterator(numberOfChunks + 1, this));
	}

};

void mergeFiles(char** fileNames, int numberOfTempFiles, __off_t outputLength, char* output_name = "out.txt") {
	MappedFile<int>* tempFiles[numberOfTempFiles];
//	MappedFile<char> output(output_name, BLOCKS_IN_CHUNK, O_RDWR | O_CREAT | O_TRUNC, outputLength * sizeof(char), PROT_WRITE);
	ofstream streamOut(output_name);

	for (int i = 0; i < numberOfTempFiles; i++) {
		tempFiles[i] = new MappedFile<int>(fileNames[i], BLOCKS_IN_CHUNK, O_RDONLY); //FIXME: PARAMETERS
	}

	MappedFile<int>::Iterator tempFileIterators[numberOfTempFiles];
	unsigned int positions[numberOfTempFiles];

	memset(&positions, 0, (numberOfTempFiles) * sizeof(unsigned int));

	for (int fileNum = 0; fileNum < numberOfTempFiles; fileNum++) {
		tempFileIterators[fileNum] = tempFiles[fileNum]->begin();
	}

	bool done = false;
	int counter = 0;

	while (!done) {
		unsigned int candidate = UINT_MAX;
		int candidateFileNum = 0;
		done = true;

		for (int fileNum = 0; fileNum < numberOfTempFiles; fileNum++) {
			if (tempFileIterators[fileNum] != tempFiles[fileNum]->end()) {
				done = false;
				if (((unsigned int*) (tempFiles[fileNum]->pMappedFile))[positions[fileNum]] < candidate) {
					candidate = ((unsigned int*) (tempFiles[fileNum]->pMappedFile))[positions[fileNum]];
					candidateFileNum = fileNum;
				}
			}
		}

		if (!done) {
			positions[candidateFileNum]++;
			if (positions[candidateFileNum] >= tempFiles[candidateFileNum]->fileStat.st_size / sizeof(int)) {

				positions[candidateFileNum] = 0;
				tempFileIterators[candidateFileNum]++;
			}

//			cout << candidate << "\t";

//			char temp[50];
//			intToChar(candidate, temp);
////			cout << temp << "!" << strlen(temp) << "!" << counter << endl;
////			cout << ".";
//			memcpy(output.pMappedFile + ((counter++) * 2), temp, strlen(temp));

			streamOut << candidate << " ";
		}
	}
	//FIXME: truncate output file (can't be more than input but can be less), file can't be read with stanatd text editor.

	for (int i = 0; i < numberOfTempFiles; i++) {
		delete (tempFiles[i]);
	}

	cout << "Merged" << endl;
}

void usage(const char* argv_0) {
	printf("Usage: %s -i <in_path> [-o <out_path>]\n"
			"\tFlags:\n"
			"\t-i <filename>  input file path\n"
			"\t-o <filename>  output file path (optional)\n"
			"\t-h display this message\n", argv_0);
}

int main(int argc, const char** argv) {
	//sort -i input.txt -o output.txt

	char * inputFileName = NULL;
	char * outputFileName = NULL;

	bool ok = false;
	//I hate parsing parameters
	for (int i = 1; i < argc - 1; i++) {
		if (strcasecmp(argv[i], "-I") == 0) {
			i++;
			int length = strlen(argv[i]);
			inputFileName = new char[length];
			memcpy(inputFileName, argv[i], length);
//			inputFileName[length] = '\0';
			ok = true;
		} else {
			if (strcasecmp(argv[i], "-O") == 0) {
				i++;
				int length = strlen(argv[i]);
				outputFileName = new char[length];
				memcpy(outputFileName, argv[i], length);
//				outputFileName[length] = '\0';
			} else {
				if (strcasecmp(argv[i], "-H") == 0) {
					usage(argv[0]);
					exit(EXIT_SUCCESS);
				} else {
					printf("Unsupported parameter \"%s\". Ignoring.\n", argv[i]);
				}
			}
		}
	}

	if (!ok) {
		printf("Wrong or insufficient input parameters.\n");
		usage(argv[0]);
		exit(EXIT_FAILURE);
	} else {
		if (outputFileName == NULL) {
			int length = strlen(defaultOutputFileName);
			outputFileName = new char[length];
			memcpy(outputFileName, defaultOutputFileName, length);
		}
	}

	//TODO: check that files are different: names not equal and not links to each other
	MappedFile<char> input(inputFileName, BLOCKS_IN_CHUNK, O_RDONLY);

	if (mkdir(".temp", 0700) != 0) {
		cout << "Couldn't create directory for temporary files: " << strerror(errno) << endl;
		if (errno != EEXIST)
			exit(EXIT_FAILURE);
	}

	int * result = new int[50000000]; //FIXME: this is awfull but how to know how many ints are there in text?
								  //IDEA: implement linked list with operator[] and pushback time O(1) or use vector
	int tail = 0;
	bool first = true;
	char** fileNames = new char*[input.numberOfChunks];

	for (MappedFile<char>::Iterator i = input.begin(); i != input.end(); i++) {
		int num = convertArrOfCharsToInts(input.pMappedFile, input.chunkSize / sizeof(char), result, tail, separator, first, input.chunkIndex == input.numberOfChunks);	//FIXME: i != input.end(
		sort(result, num, quick);
		fileNames[input.chunkIndex] = tempnam(".temp", "tmp_"); //XXX: valgrind says that here we loose some memory but I dont know if I can fix it anyway
		MappedFile<int> output = MappedFile<int>(fileNames[input.chunkIndex], BLOCKS_IN_CHUNK, O_RDWR | O_CREAT | O_TRUNC, num * sizeof(int), PROT_WRITE);
		memcpy(output.pMappedFile, result, num * sizeof(int));
		cout << endl;
	}

//	for (int i = 0; i <= input.numberOfChunks; ++i) {
//		cout << fileNames[i] << endl;
//	}

	mergeFiles(fileNames, input.numberOfChunks + 1, input.fileStat.st_size / sizeof(char), outputFileName);

	//free all allocated resources
	for(int i = 0; i <= input.numberOfChunks; i++){
		if (remove(fileNames[i]) != 0){
			cout << "Error deleting temporary file " << fileNames[i] << ": " << strerror(errno) << endl;
		}
	}

	for (int i = 0; i <= input.numberOfChunks; i++) {
		free(fileNames[i]);	//XXX: freeing this causes crashes on big files???
	}
	delete[] (fileNames);	//XXX: freeing this causes crashes on big files???
	delete[] (result);
	delete[] (outputFileName);
	delete[] (inputFileName);
	if (rmdir(".temp") != 0){
		cout << "Error removing directory " << ".temp" << ": " << strerror(errno) << endl;
	}

	cout << "Exited" << endl;

	return (0);
}
